package BiTree;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: java_concurrent
 * @description: 求两个节点的最近公共祖先
 * @author: lxf
 * @create: 2024-07-15 17:01
 **/
public class LowestCommonAncestor2 {


    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(8, null, null);
        TreeNode node6 = new TreeNode(4);
        TreeNode node5 = new TreeNode(2, new TreeNode(7), node6);
        TreeNode node4 = new TreeNode(6, null, null);
        TreeNode node3 = new TreeNode(1, new TreeNode(0), node7);
        TreeNode node2 = new TreeNode(5, node4, node5);
        TreeNode node1 = new TreeNode(3, node2, node3);
        TreeNode node = lowestCommonAncestor(node1, node2, node3);
        System.out.println(node.val);
    }


    // 从下往上遍历，如果该节点满足p/q，直接返回
    // 获取左子树的解与右子树的解
    // 如果任意有符合节点，代表p和q属于有解的子树中
    // 如果都有解，代表p和q属于不同子树中，返回本身节点
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null && right == null){return null;}
        if (left == null && right != null){return right;}
        if (left != null && right == null){return left;}
        return root;
    }
}
